import java.util.Arrays;

/**
 * 1046. 最后一块石头的重量
 * https://leetcode-cn.com/problems/last-stone-weight/
 */
public class Solutions_1046 {
    public static void main(String[] args) {
//        int[] nums = {2, 7, 4, 1, 8, 1};  // output: 1
        int[] nums = {1, 3};  // output: 2

//        解释：
//        先选出 7 和 8，得到 1，所以数组转换为 {2, 4, 1, 1, 1}，
//        再选出 2 和 4，得到 2，所以数组转换为 {2, 1, 1, 1}，
//        接着是 2 和 1，得到 1，所以数组转换为 {1, 1, 1}，
//        最后选出 1 和 1，得到 0，最终数组转换为 {1}，这就是最后剩下那块石头的重量。

        int result = lastStoneWeight(nums);
        System.out.println(result);
    }

    /**
     * 排序
     */
    public static int lastStoneWeight(int[] stones) {
        int len = stones.length;
        // 碰撞 len - 1 次，剩余最后一个石头
        for (int i = 0; i < len - 1; i++) {
            // 每次都排序
            Arrays.sort(stones);
            // 取出两个较大的
            int o1 = stones[len - 1];
            int o2 = stones[len - 2];
            // 较小的一个，碰撞后，剩余 0
            stones[len - 2] = 0;
            // 较小的一个，碰撞后，剩余 o1 - o2 的重量
            stones[len - 1] = o1 - o2;
        }
        // 最终的 stones[len - 1] 即是最终剩余的 1 个石头
        return stones[len - 1];
    }
}
